﻿using System;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_154 : BaseProblem
    {
        private static Dictionary<long, long> fac2 = new Dictionary<long, long>();
        private static Dictionary<long, long> fac5 = new Dictionary<long, long>();

        public override object GetResult()
        {
            const long max = 200000;
            const long mult = 12;

            //const long max = 20;
            //const long mult = 1;

            long mxRs2 = 0;
            long mxRs5 = 0;
            GetVals(max, ref mxRs2, ref mxRs5);
            BigInteger res = 0;

            for (int i = 0; i <= max; i++)
            {
                long i2 = 0;
                long i5 = 0;
                GetVals(max-i, ref i2, ref i5);
                if (Math.Min(mxRs2-i2, mxRs5 - i5) < mult)
                    continue;
                for (int j = 0; j <= i; j++)
                {
                    long j2 = 0;
                    long j5 = 0;
                    GetVals(j, ref j2, ref j5);
                    if (Math.Min(mxRs2 - i2-j2, mxRs5 - i5-j5) < mult)
                        break;
                    long ji2 = 0;
                    long ji5 = 0;
                    GetVals(i-j, ref ji2, ref ji5);
                    if (Math.Min(mxRs2 - i2 - j2-ji2, mxRs5 - i5 - j5-ji5) >= mult)
                        res++;
                }
            }
            return res;
        }

        private static void GetVals(long value, ref long res2, ref long res5)
        {
            if (fac2.ContainsKey(value))
            {
                res2 = fac2[value];
                res5 = fac5[value];
                return;
            }
            var tmp = value;
            res2 = 0;
            while (tmp >= 2)
            {
                res2 += tmp/2;
                tmp /= 2;
            }
            tmp = value;
            res5 = 0;
            while (tmp >= 5)
            {
                res5 += tmp / 5;
                tmp /= 5;
            }
            fac2.Add(value, res2);
            fac5.Add(value, res5);
            return;
        }

        public override string Problem
        {
            get
            {
                return @"A triangular pyramid is constructed using spherical balls so that each ball rests on exactly three balls of the next lower level.


Then, we calculate the number of paths leading from the apex to each position:

A path starts at the apex and progresses downwards to any of the three spheres directly below the current position.

Consequently, the number of paths to reach a certain position is the sum of the numbers immediately above it (depending on the position, there are up to three numbers above it).

The result is Pascal's pyramid and the numbers at each level n are the coefficients of the trinomial expansion (x + y + z)n.

How many coefficients in the expansion of (x + y + z)200000 are multiples of 1012?";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 479742450;
            }
        }

    }
}
